#define _CRT_SECURE_NO_WARNINGS 1
//#include<stdio.h>
//
//
//void CharPyramid(int n, char ch)
//{
//	int i = 0;
//	int j = 0;
//	for (i = 1; i <= n; i++)
//	{
//		
//		for (j = 0; j < n - i; j++)
//		{
//			printf(" ");
//		}
//		for (j = 0; j < i; j++)
//		{
//			printf("%c ", ch);
//		}
//		if (i < n)
//		{
//			printf("\n");
//		}
//	}
//}
//
//int main()
//{
//	int n = 0;
//	char ch = '0';
//	scanf("%d %c", &n, &ch);
//	CharPyramid(n, ch);
//	return 0;
//}


//void hollow_pyramid(n)
//{
//	int i = 0;
//	int j = 0;
//	for (i = 1; i <= n; i++)
//	{
//		int i1 = i - 1;
//		for (j = 0; j < n - i; j++)
//		{
//			printf(" ");
//		}
//		printf("%d", i);
//		if (i == 1)
//		{
//			printf("\n");
//		}
//		if (i > 1 && i < n)
//		{
//			for (j = 1; j <= 2 * i1 - 1; j++)
//			{
//				printf(" ");
//			}
//			printf("%d\n", i);
//			
//		}
//		if (i == n)
//		{
//			for (j = 1; j < 2 * i - 1; j++)
//			{
//				printf("%d", i);
//			}
//		}
//		
//	}
//}
//
//#include<stdio.h>
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	hollow_pyramid(n);
//	return 0;
//}

//#include<stdio.h>
//#include<math.h>
//int prime(int p)
//{
//	int i = 0;
//	for (i = 2; i <= sqrt(p);i++)
//	{
//		if (p % i == 0)
//		{
//			break;
//		}
//	}
//	if (i > sqrt(p))
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//}
//
//int prime_sum(int m, int n)
//{
//	int sum = 0;
//	int p = 0;
//	for (p = m; p <= n; p++)
//	{
//		if (1 == prime(p))
//		{
//			sum += p;
//		}
//
//	}
//	return sum;
//}
//
//int main()
//{
//	int m = 0;
//	int n = 0;
//	int p = 0;
//	int ret = 0;
//	
//	scanf("%d %d", &m, &n);
//	printf("Sum of ( ");
//	if (m == 1)
//	{
//		m = 2;
//	}
//	for (p = m; p <= n; p++)
//	{
//		ret = prime(p);
//		if (ret == 1)
//		{
//			printf("%d ", p);
//		}
//	}
//	
//	prime_sum(m, n);
//	printf(") = %d", prime_sum(m, n));
//	
//	return 0;
//}

//#include<stdio.h>
//
//int countdigit(number, digit)
//{
//	int count = 0;
//	int i = 0;
//	if (number != 0)
//	{
//		for (i = number; i > 0; i /= 10)
//		{
//			if (i % 10 == digit)
//			{
//				count++;
//			}
//		}
//		return count;
//	}
//	else if (number == 0 && digit == 0)
//	{
//		return 1;
//	}
//}
//
//int main()
//{
//	int tmp = 0;
//	int number = 0; 
//	int digit = 0;
//	scanf("%d %d", &number, &digit);
//	tmp = number;
//	
//	if (number < 0)
//	{
//		number = -1 * number;
//	}
//	countdigit(number,digit);
//	printf("Number of digit %d in %d: %d", digit, tmp, countdigit(number, digit));
//	return 0;
//}

#include<stdio.h>

//int factorsum(int num)
//{
//	int i = 0;
//	int sum = 0;
//	for (i = 1; i < num; i++)
//	{
//		if (num % i == 0)
//		{
//			sum += i;
//		}
//	}
//	return sum;
//}
//
//void print_pn(int m, int n)
//{
//	int i = 0;
//	int  j = 0;
//	int sum = 0;
//	int arr[100] = { 0 };
//	int count = 0;
//	int k = 0;
//	int flag = 0;
//	for (i = m; i < n; i++)
//	{
//		k = 0;
//		count = 0;
//		sum = 0;
//		for (j = 1; j < i; j++)
//		{
//			if (i % j == 0)
//			{
//				arr[k] = j;
//				sum += j;
//				count++;
//				k++;
//			}
//		}
//		if (sum == i)
//		{
//			flag++;
//			printf("%d = ", sum);
//			for (k = 0; k < count; k++)
//			{
//				printf("%d", arr[k]);
//				if (k < count - 1)
//				{
//					printf(" + ");
//				}
//			}
//			printf("\n");
//		}
//	}
//	if (flag == 0)
//	{
//		printf("No perfect number");
//	}
//}
//
//
//int factorsum(int num)
//{
//	int i = 0;
//	int sum = 0;
//	for (i = 1; i < num; i++)
//	{
//		if (num % i == 0)
//		{
//			sum += i;
//		}
//	}
//
//	return sum;
//	
//	
//}
//
////void print_pn(int num)
////{
////	int i = 0;
////	printf("%d = ", num);
////	for (i = 1; i < num; i++)
////	{
////		if (num % i == 0)
////		{
////			printf("%d", i);
////			if()
////		}
////	}
////}
//
//int main()
//{
//	int m = 0;
//	int n = 0;
//	int num = 0;
//	scanf("%d %d", &m, &n);
//	for (num = m; num <= n; num++)
//	{
//		factorsum(num);
//			
//		
//		
//	}
//	print_pn(m, n);
//	return 0;
//}



//#include<stdio.h>
//
//int fib(int n)
//{
//	int a = 1;
//	int b = 1;
//	int c = 0;
//	int i = 0;
//	if (n <= 2)
//	{
//		return 1;
//	}
//	else
//	{
//		for (i = 0; i < n - 2; i++)
//		{
//			c = a + b;
//			b = c;
//			a = b;
//		}
//		return c;
//	}
//}
//
//void print_fn(int m, int n)
//{
//	int i = 0;
//	int a = 1;
//	int b = 1;
//	int c = 0;
//	int flag = 0;
//	if (m <= 2)
//	{
//		printf("1 ");
//		printf("1 ");
//		while (c <= n)
//		{
//			
//			c = a + b;
//			a = b;
//			b = c;
//
//			if (c <= n && c >= m)
//			{
//				printf("%d ", c);
//				flag++;
//			}
//			
//		}
//	}
//	else
//	{
//		
//		while (c <= n)
//		{
//			
//			c = a + b;
//			a = b;
//			b = c;
//			if (c <= n && c >= m)
//			{
//				printf("%d ", c);
//				flag++;
//			}
//		}
//	}
//	if (flag == 0)
//	{
//		printf("No Fibonacci number");
//	}
//}
//
//int main()
//{
//	int m = 0;
//	int n = 0;
//	scanf("%d %d", &m, &n);
//	fib(n);
//	print_fn(m, n);
//	return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//	int x = 0;
//	int y = 0;
//	int n = 0;
//	int t = 0;
//	int i = 0;
//	int j = 0;
//	int same = 0;
//	scanf("%d", &t);
//	for (i = 0; i < t; i++)
//	{
//		scanf("%d %d %d", &x, &y, &n);
//		for (j = x > y ? x + 1 : y + 1; j > 0; j--)
//		{
//			if ((x + 1) % j == 0 && (y + 1) % j == 0)
//			{
//				break;
//			}
//		}
//		same = ((x + 1) * (y + 1)) / j;
//		if (x != 0 && y != 0)
//		{
//			if (x == y)
//			{
//				if (n < x + 1)
//				{
//					printf("0\n");
//				}
//				else
//				{
//					printf("%d\n", 36 * (n / (x + 1)));
//				}
//
//			}
//			else
//			{
//				if (n < same)
//				{
//					printf("0\n");
//				}
//				else
//				{
//					printf("%d\n", 36 * (n / same));
//				}
//			}
//		}
//		else if (x == 0 && y != 0)
//		{
//			if (n < y + 1)
//			{
//				printf("0\n");
//			}
//			else
//			{
//				printf("%d\n", 36 * (n / (y + 1)));
//			}
//		}
//		else if (x != 0 && y == 0)
//		{
//			if (n < x + 1)
//			{
//				printf("0\n");
//			}
//			else
//			{
//				printf("%d\n", 36 * (n / (x + 1)));
//			}
//		}
//		else
//		{
//			printf("%d\n", 36 * n);
//		}
//	}
//	return 0;
//}



//#include<stdio.h>
//#include<stdlib.h>
//#include<string.h>
//int main()
//{
//	int count = 0;
//	int n = 0;
//	int i = 0;
//	int ch = 0;
//	int count1 = 0;
//	scanf("%d", &n);
//	getchar();
//	/*getchar();*/
//	while (count < n)
//	{
//		ch = getchar();
//		if (count1 == 0)
//		{
//			if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z'))
//			{
//				putchar(ch);
//				count++;
//				count1++;
//			}
//			/*else if (ch == ' ')
//			{
//				count++;
//			}*/
//			else if (ch == '#')
//			{
//				break;
//			}
//		}
//		else
//		{
//			if (ch >= 'A' && ch <= 'Z')
//			{
//				printf(" ");
//				putchar(ch);
//				count += 2;
//			}
//			else if (ch >= 'a' && ch <= 'z')
//			{
//				putchar(ch);
//				count++;
//			}
//			else if (ch == '#')
//			{
//				break;
//			}
//			/*else if (ch == ' ')
//			{
//				count++;
//			}*/
//		}
//	}
//	return 0;
//}